package everything.search.trees;

import java.util.Map;
import java.util.TreeMap;

import everything.WorldMap;
import everything.search.AgentState;
import everything.search.agents.IntelligentAgent;
import everything.search.trees.nodes.GameTreeNode;

public class GameTreeSearchWithPruning extends GameTreePruningSearch{


	public GameTreeSearchWithPruning(WorldMap map, int id, int idOp){
		super(map, id, idOp);
	}
	
	@Override
	protected GameTreeNode searchWithParam(AgentState state, int ply) {
		GameTreeNode node = new GameTreeNode(state, null, 0, null);
		GameTreeNode n = searchMax(node, ply, Integer.MIN_VALUE ,Integer.MAX_VALUE);
		node.setValue(n.getValue());
		return n;
	}


//	public GameTreeNode search(AgentState state, int ply){
//		GameTreeNode node = new GameTreeNode(state, null, 0, null);
//		log("STARTING SEARCH FOR " + _id + " ("+ply+") WITH " + state);
//		GameTreeNode searchNode = searchMax(node, ply, Integer.MIN_VALUE ,Integer.MAX_VALUE);
//		node.setValue(searchNode.getValue());
//		GameTreeNode tmp = searchNode;
//		while (tmp.getParent()!=null){
//			System.out.println("BACKTRACK: " + tmp.getMove() + "  "+tmp.getValue()+" " + tmp.getState());
//			tmp = tmp.getParent();
//		}
//		System.out.println("BACKTRACK: " + tmp.getMove() + "  "+tmp.getValue()+" " + tmp.getState());
//		return searchNode;
//	}

	protected GameTreeNode searchMax(GameTreeNode node, int ply, double alpha, double beta){
		AgentState state = node.getState();
		
		GameTreeNode storedState = checkState(state); 
		if (storedState!=null){
			return storedState;
		}
		
		Map<String, AgentState> expansions = new TreeMap<String, AgentState>();
		expansions.put("North", getNextState(state, "North", false));
		expansions.put("South", getNextState(state, "South", false));
		expansions.put("West", getNextState(state, "West", false));
		expansions.put("East", getNextState(state, "East", false));
		expansions.put("Fire", getNextState(state, "Fire", false));


		GameTreeNode optimalValue = null;
		for (Map.Entry<String, AgentState> t: expansions.entrySet()){
			if (t.getValue().isTerminal() || ply == 0){
				double utility = IntelligentAgent.utility(_id, t.getValue(),_map);
				if (optimalValue == null || utility > optimalValue.getValue()){
					node.setValue(utility);
					optimalValue = new GameTreeNode(t.getValue(), node, utility, t.getKey());
				}
				alpha = Math.max(optimalValue.getValue(), alpha);
				log("Found terminal - " + _id +" - MAX (" +ply+") ["+utility+"]: " + t.getValue() + "  " + t.getKey());
			} else {
				GameTreeNode subTreeRoot = new GameTreeNode(t.getValue(), node, Integer.MAX_VALUE, t.getKey());
				GameTreeNode subTreeAns = searchMin(subTreeRoot, ply-1, alpha, beta);
				// found better value
				log("Expanding - " + _id +" - MAX (" +ply+") ["+subTreeAns.getValue()+"]: " + t.getValue() + "  " + t.getKey());
				if (optimalValue == null || subTreeAns.getValue() > optimalValue.getValue()){
					subTreeRoot.setValue(subTreeAns.getValue());
					optimalValue = subTreeAns;
					alpha = Math.max(optimalValue.getValue(), alpha);
					if (optimalValue.getValue() >= beta){
						log(beta + " beta sup");
						storeState(state, optimalValue);
						return optimalValue;
					}
				}
			}
		}
		storeState(state, optimalValue);
		return optimalValue;

	}
	protected GameTreeNode searchMin(GameTreeNode node, int ply, double alpha, double beta){

		AgentState state = node.getState();
		
		GameTreeNode storedState = checkState(state); 
		if (storedState!=null){
			return storedState;
		}
			
		Map<String, AgentState> expansions = new TreeMap<String, AgentState>();
		expansions.put("North", getNextOpState(state, "North", false));
		expansions.put("South", getNextOpState(state, "South", false));
		expansions.put("West", getNextOpState(state, "West", false));
		expansions.put("East", getNextOpState(state, "East", false));
		expansions.put("Fire", getNextOpState(state, "Fire", false));

		if (ply ==4)
			System.out.println(alpha + "  " + beta);
		GameTreeNode optimalValue = null;
		for (Map.Entry<String, AgentState> t: expansions.entrySet()){
			if (t.getValue().isTerminal()){
				double utility = IntelligentAgent.utility(_id, t.getValue(), _map);
				if (optimalValue == null || utility < optimalValue.getValue()){
					node.setValue(utility);
					optimalValue = new GameTreeNode(t.getValue(), node, utility, t.getKey());
				}
				beta = Math.min(optimalValue.getValue(), beta);
				log("Found terminal - " + _id +" - MIN (" +ply+") ["+utility+"]: " + t.getValue() + "  " + t.getKey());
			} else {
				GameTreeNode subTreeRoot = new GameTreeNode(t.getValue(), node, Integer.MIN_VALUE, t.getKey());
				GameTreeNode subTreeAns = searchMax(subTreeRoot, ply-1, alpha, beta);
				log("Expanding - " + _id +" - MIN (" +ply+") ["+subTreeAns.getValue()+"]: " + t.getValue() + "  " + t.getKey());
				if (optimalValue == null || subTreeAns.getValue() < optimalValue.getValue()){
					subTreeRoot.setValue(subTreeAns.getValue());
					optimalValue = subTreeAns;
					beta = Math.min(optimalValue.getValue(), beta);
					if (optimalValue.getValue() <= alpha) {
						log(alpha + " alpha sup");
						storeState(state, optimalValue);
						return optimalValue;
					}
				}
			}
		}
		storeState(state, optimalValue);
		return optimalValue;
	}
}
